import java.util.*;

public class NonDecreasingSubsequences0103_491 {

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();


    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums,0);
        return result;
    }

    private void backTracking(int[] nums, int startIndex) {
        if(path.size() > 1) {
            result.add(new ArrayList<>(path));
            // 注意这里不要加return，因为要取树上的所有节点
        }

        Set<Integer> set = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {
            if((!path.isEmpty() && nums[i] < path.getLast()) || set.contains(nums[i])) continue;

            set.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums,i+1);
            path.removeLast();
        }
    }


}
